// https://www.lintcode.com/problem/implement-trie-prefix-tree/my-submissions

class TrieNode 
{
    public: //public 别忘了
    TrieNode** sons; //注意 指针数组
    bool isWord;  
    string word;
    TrieNode() {
        sons = new TrieNode*[26]; //注意 指针数组
        for (int i = 0; i < 26; ++i)
        {
            sons[i] = NULL;
        }
        isWord = false;
    }
};
class Trie {
public:
    TrieNode *root;
    Trie() {
        root = new TrieNode;
    }

    /*
     * @param word: a word
     * @return: nothing
     */
    void insert(string &word) {
        TrieNode *tmp = root;
        for (int i = 0; i < word.size(); ++i)
        {
            int idx = word[i] - 'a';
            if (!tmp->sons[idx])
            {
                tmp->sons[idx] = new TrieNode;
            }
            tmp = tmp->sons[idx];
            // tmp->isWord = true;
        }
        tmp->isWord = true;
    }

    /*
     * @param word: A string
     * @return: if the word is in the trie.
     */
    bool search(string &word) {
        TrieNode *tmp = root;
        for (int i = 0; i < word.size(); ++i)
        {
            int idx = word[i] - 'a';
            if (!tmp->sons[idx])
            {
                return false;
            }
            tmp = tmp->sons[idx];
        }
        return tmp->isWord;
    }

    /*
     * @param prefix: A string
     * @return: if there is any word in the trie that starts with the given prefix.
     */
    bool startsWith(string &prefix) {
        TrieNode *tmp = root;
        for (int i = 0; i < prefix.size(); ++i)
        {
            int idx = prefix[i] - 'a';
            if (!tmp->sons[idx])
            {
                return false;
            }
            tmp = tmp->sons[idx];
        }
        return true;
    }
};